package gold.gold01;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * ascii码表, 如果只有数字和基本的英文标点, 则只在0~127范围内
 * 或使用一个 int map = new int[256]; 这样就差不多了
 */
public class S0104回文排列 {
    // 68, 44
    public boolean canPermutePalindrome(String s) {
        if(s == null) return false;
        HashMap<Character, Integer> map = new HashMap<>();
        for(char c: s.toCharArray()){
            if(map.containsKey(c)){
                // 这里从replace改成put, 降低了不少内存消耗, 时间消耗因为软件精度问题显示不了区别
                map.replace(c, map.get(c) % 2 == 0? 1: 0);
            }else {
                map.put(c, 1);
            }
        }
        int flag = 1;
        for(int i: map.values()){
            if(i == 1){
                flag --;
                if(flag < 0) return false;
            }
        }
        return true;
    }

    // 这种只需要判断奇偶的, 直接使用set来remove和add不就行了, 我傻了
    public boolean canPermutePalindrome2(String s) {
        if(s == null){
            return false;
        }
        char[] chars = s.toCharArray();
        // 注意这里的set的实践，其实主要就是hashSet
        Set<Character> set = new HashSet<>();
        for(char c : chars){
            if(set.contains(c)){
                set.remove(c);
            }else{
                set.add(c);
            }
        }
        return set.size() <= 1;
    }

    // 思路不行，还不如hashMap统计数量，
    // xxxx反正是判断字符，分割开，排个序，看一下奇数位是不是和偶数位一样，然后最后剩一个/0个
    public boolean canPermutePalindrome3(String s) {
        // char[]有点烦，直接string[]吧
        String[] sArray = s.split("");
//        System.out.println(Arrays.toString(sArray));
//        System.out.println(String.join("", sArray));
        Arrays.sort(sArray);
        // 完美跳过奇偶, 不行，排序后并不能保证出现单个的那一个在最后面的情况
        for(int i = 0; i < sArray.length / 2; i ++){
            if(!sArray[i * 2].equals(sArray[i * 2 + 1])){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new S0104回文排列().canPermutePalindrome(" 阿道夫阿道夫"));
        System.out.println(new S0104回文排列().canPermutePalindrome3("carerac"));
    }
}
